package com.monkeyboy.list;


import com.monkeyboy.ListNode;

/**
 * 反转链表
 * 解题思路：
 * 第一种就是采用递归的方式，分别让下一个节点的next指向上一个节点
 * 第二种就是非常经典的头插法（常用）
 *
 * @Author Gavin
 * @date 2021.04.03 12:09
 */
public class List06 {


    //递归处理
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {//这两个判断可以确保递归中head不为null
            return null;
        }
        ListNode next = head.next;
        head.next = null;//关键点1，先使节点的next为null，因为要翻转，由于是递归，所以这一步基本会让所有节点全部分离开，然后通过
        //下面的next.next进行重写组装，最后返回最后一个节点就行了
        ListNode newHead = reverseList(next);//
        next.next = head;//实现翻转，让next指向head
        return newHead;
    }


    //使用头插法，这个方法不错，好好理解下
    /**
     * 思路就是newHead一个节点始终指着头节点的指针，然后遍历原来的list，每遍历一个就把这个节点和new的这个节点做交互
     * 因为new的这个节点始终指向头节点，循环一个节点就把这个节点的next指向newHead.next(),然后newHead.next就为这个循环的节点
     */
    public ListNode reverseList2(ListNode head) {
        ListNode newList = new ListNode(-1);
        while (head != null) {
            ListNode next = head.next;
            head.next = newList.next;
            newList.next = head;
            head = next;
        }
        return newList.next;
    }

    public static void main(String[] args) {

    }
}
